package leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Ghost on 2014/11/22.
 */

public class Surrounded_Regions {
    class Point {
        int i, j;

        Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public void solve(char[][] board) {

        int m = board.length;
        if (m == 0)
            return;
        int n = board[0].length;
        if (n == 0)
            return;
        Queue<Point> queue = new LinkedList<Point>();
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                board[i][0] = '0';
                if (1 < n - 1 && board[i][1] == 'O') {
                    queue.add(new Point(i, 1));
                }
            }
            if (board[i][n - 1] == 'O') {
                board[i][n - 1] = '0';
                if (n > 2 && board[i][n - 2] == 'O')
                    queue.add(new Point(i, n - 2));
            }
        }

        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {
                board[0][i] = '0';
                if (1 < m - 1 && board[1][i] == 'O')
                    queue.add(new Point(1, i));
            }
            if (board[m - 1][i] == 'O') {
                board[m - 1][i] = '0';
                if (m > 2 && board[m - 2][i] == 'O')
                    queue.add(new Point(m - 1, i));
            }
        }


        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x, y;
            board[point.i][point.j] = '0';
            x = point.i - 1;
            y = point.j;
            if (x >= 0 && board[x][y] == 'O') {
                queue.add(new Point(x, y));
            }

            x = point.i + 1;
            y = point.j;
            if (x < m && board[x][y] == 'O') {
                queue.add(new Point(x, y));
            }

            x = point.i;
            y = point.j - 1;
            if (y >= 0 && board[x][y] == 'O')
                queue.add(new Point(x, y));

            x = point.i;
            y = point.j + 1;
            if (y < n && board[x][y] == 'O')
                queue.add(new Point(x, y));
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '0')
                    board[i][j] = 'O';
            }

        }
    }

    /*
    Input:	["XO","OX"]
    Output:	["OO","OX"]
    Expected:	["XO","OX"]

    * */
    public static void main(String[] args) {
        char[][] board = {{'O', 'O', 'X', 'X', 'X', 'O'}, {'O', 'X', 'O', 'O', 'X', 'X'},
                {'O', 'X', 'O', 'X', 'X', 'X'}, {'X', 'O', 'X', 'O', 'O', 'X'}};
        char[][] board2 = {{'X','O'}};
        Surrounded_Regions surrounded_regions = new Surrounded_Regions();
        surrounded_regions.solve(board2);
        for (char[] aBoard : board2) {
            for (int j = 0; j < board2[0].length; j++) {
                System.out.print(" " + aBoard[j]);
            }
            System.out.println();
        }
    }
}
